Exercise (Week 3)
Table of Contents
DUE: Fri June 23 10:59:59 AM
1 Getting Started
Before you begin, make sure that you installed Haskell according to the Haskell Setup instructions. To get started, follow the instructions below.
Download the exercise zipfile and extract it to a directory in your home directory at CSE.
This zipfile contains a file, called Ex02.hs, wherein you will do all of your programming.
To test your code, run the following shell commands to open a GHCi session:
$ 3141 newclass starting new subshell for class COMP3141... $ cabal repl ... *Ex02>
(Ignore the -Wmissing-home-modules warning if you get one.)
Note that you will only need to submit Ex02.hs, so only make changes to that file.
Download the exercise zipfile and extract it to a directory on your local machine.
This zipfile contains a file, called Ex02.hs, wherein you will do all of your programming.
To test your code, run the following shell commands to open a GHCi session:
$ stack repl
Configuring GHCi with the following packages: Ex02
Using main module: 1. Package 'Ex02' component exe:Ex02 ...
GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Ex02 (Ex02.hs, interpreted)
Ok, one module loaded.
*Ex02>
Note that you will only need to submit Ex02.hs, so only make changes to that file.
2 Part 1: Promoting Semigroups (3 Marks)
In this part you will establish that any semigroup can be "promoted" to a monoid simply by adjoining a new element to the underlying set, and decreeing that this new element should act like the monoid identity.
More formally: if you start with a semigroup consisting of
\begin{equation*} \mathtt{S} \text{ (the underlying type/set)} \end{equation*} \begin{equation*} \bullet \mathtt{:: S \rightarrow S \rightarrow S} \text{ (the semigroup operation)} \end{equation*}
then you can pick some e that does not belong to the set S (i.e. is distinct from all elements of S),
and define a larger set
and a new operation o on S' given by the following equations:
No matter which semigroup you start with, the set S', the opertion o, and the identity element e together form a monoid.
Your tasks in this exercise are all related to the construction above.
In the Haskell code of Ex02.hs, the construction of the type S' is done by data Promote s = ....
Define semigroup and monoid operations on Promote s corresponding to o above (promoteOp).
Implement two generic predicates that QuickCheck can use to test if a given monoid operation is lawful.
The first of these (testAssoc) should test that the monoid operation is indeed associative,
while the second (testUnit) should test that the identity element satisfies the required laws.
Important: A complete solution of Part 1 must have working definitions of all the undefined functions
in Part 1 of Ex02.hs. These include promoteOp, (<>), mempty, mappend, testAssoc and testUnit.
3 Part 2: Order Monoids (2 Marks)
In this part you will establish that any type with a total order (i.e. instance of the Ord type class)
gives rise to a monoid where the monoid operation corresponds to taking the minimum.
Given an ordered type t, you will define your monoid structure on the type `data MinMonoid t = EmbMM t | Infinity`.
Define a monoid operation <> on MinMonoid t in such a way that given any list [x1,x2,...,xn] of values,
evaluating EmbMM x1 <> EmbMM x2 <> ... <> EmbMM xn results in EmbMM xi, where xi denotes the minimum element
of the list [x1,x2,...,xn]. For example, on Int, EmbMM 2 <> EmbMM 1 <> EmbMM 3 should evaluate to EmbMM 1.
Define lawful Semigroup and Monoid type class instaces for MinMonoid using the operation defined above.
4 Part 3: The Sparse List Monoid (4 Marks)
A sparse list is an alternative representation of lists, designed to require less memory for lists where adjacent elements are mostly equal.
newtype SparseList a = SparseList [(Int,a)] deriving (Show,Eq)
For example, the Char list
['a','a','a','b','b','a','a']
Is represented as follows in a SparseList:
SparseList [(3,'a'),(2,'b'),(2,'a')]
Define, as a generic function of signature (Eq a) => [(Int,a)] -> Bool,
what it means for a list to be sorted well-formed.
Implement a functionally correct append operation append that takes
two sparse lists as input, and yields a sparse list as output.
Write a QuickCheck-testable predicate that tests that merging two sparse lists indeed results in a sparse list.
Define a monoid instance for sparse lists equipped with an append operation, and write tests for the monoid laws.
5 Submission Instructions
While connected/using a CSE machine, type the following to submit your
work from the directory within the Ex02 folder:
$ give cs3141 ex02 Ex02.hs
Alternatively, if the above does not work, try the give web interface.
Your submission should work on ghc version on the CSE lab system,
which is ghc 8.8.4. Using a different ghc version on your home
machine is fine and unlikely to lead to problems. When you submit, a
subset of the marking test suite will run on the ghc version
mentioned above. The first time, this may take a while as dependencies
are installed. If you see some of them failing, you may want to go
back to the drawing board and submit again. give allows you to
resubmit as many times as you want before the deadline; only the last
submission counts.
Do not remove any of the declarations from the template, do not change
their type, and do not move them into a local scope (such as a let
or where block). We won't be able to test your submission if so.
Note that you will submit only the Haskell module file called
Ex02.hs (and not the entire project).
All work submitted for assessment must be entirely your own. Unacknowledged copying of material, in whole or part, is a serious offence. Before submitting any work you should read and understand the UNSW Plagiarism Policy.